Traditionally, characters have been printed using metal type which allows very detailed rendering of a character, including subtle curves and very fine lines. A character may be alphanumeric, an Oriental or other foreign language character, or even a fanciful design and may be printed in a variety of point sizes. In modern computer devices, characters are defined on raster devices such as video display terminals or laser printers or by using a multi-pin print head. Characters can be printed on a surface or displayed on a video screen as a series of dots which are printed or turned on in order to approximate as closely as possible the ideal shape of the character. When characters are small enough relative to the resolution of the display device, choosing which pixels should be displayed to accurately represent the character becomes more complex than when the character is large. A typical video monitor can display about 72 pixels per inch. At this resolution it is difficult to display legibly most type faces smaller than about twenty pixels tall.
An ideal representation of the character is usually defined in "character space" at very high resolution as one or more areas bounded by an outline or path. A character consists of one or more continuous black areas. For instance the letter "O" consists of a single closed loop, the letter "d" consists of a loop connected to a line and the letter "i" consists essentially of a dot a short distance away from a line which may have additional details such as serifs. One way of describing a character involves defining an outline of the outer edge of each contiguous black portion of the character and then filling that outline to display the character. Since characters are usually printed in dark ink on a light background, one can describe filled areas as black but one skilled in the art will recognize that the method of this invention can be used to determine what pixels are candidates for display using any of many fill methods, including characters which are light on a dark background, commonly used in video displays, or characters on backgrounds having a different color are also within the teachings of this invention. The outline is preferably defined as one or more paths, each of which is usually traced in one direction, either clockwise or counter-clockwise. Each path can be represented as a sequential series of curves and/or linear line segments called edges. If a black area has interior white spaces as, for instance, in the letter "O", each interior white area can also be defined by a path consisting of a series of edges.
When a character is displayed on a raster device, those pixels which fall within the black area of the character should be displayed, that is, they should be printed on a surface or turned on for a video display. At high resolution or when the character is very large, multiple pixels may fall within each black area and the character can be displayed in great detail. When the character is reduced to a small size, however, or the resolution of the device is limited, certain black areas may no longer cover multiple pixels and in fact may cover only a fraction of a pixel. Displaying small characters on a device of limited resolution has been a persistent problem in the past. "n", "s" and "e" on a 6.times.7 matrix and in FIG. 2 by an italic character "e" on an 8.times.8 matrix of pixels. In FIG. 2A the outline of the character "e" is illustrated as filled at very high resolution (light gray) and low resolution (darker gray). The raster display, however, can only turn on or off entire pixels, which corresponds to the darker gray.
One prior approach to this problem is the center point fill method and the improved fill method described in the copending application entitled "Connected-Run Dropout-Free Center Point Fill Method For Displaying Characters" by the same inventors and filed on Jun. 15, 1990. One problem that occurs with many fill methods is that certain character features may be found in close proximity. As the display resolution decreases the pixel fill method chosen sometimes turns on pixels that cause parts of the character bitmap to touch each other that actually should not be in contact. This introduces errors in the topology of the character that greatly reduce the legibility. For example, in FIGS. 1A, 1B and 1C the "n" closes in at the bottom instead of having an open space between the legs, and the curves of the "e" and the "s" both touch the main body of the character and change the bitmap into something like a small "8". In FIG. 2A, the italic "e" is difficult to read.
One method of resolving these problems is described in U.S. patent application Ser. No. 07/388,339, now abandoned in favor of continuation application Ser. No. 07/775,267, filed Oct. 11, 1991, entitled "Method For Editing Character Bitmaps at Small Sizes". That application describes how to turn on pixels according to the outline of a character using one of the fill rules such as center point fill, and modify the display by turning off or moving pixels that cause the character to close improperly. The present invention provides a faster method for modifying the display by turning off or moving pixels that cause the character to close improperly.